#include <iostream>

void MaxHeap(int * a, int n, int i)
{
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int maxIndex = i;
    if(left < n && a[left] > a[i])
    {
        maxIndex = left;
    }
    if(right < n && a[right] > a[maxIndex])
    {
        maxIndex = right;
    }
    if(maxIndex != i)
    {
        std::swap(a[i],a[maxIndex]);
        MaxHeap(a,n,maxIndex);
    }
}

void HeapSort(int * a, int n)
{
    //第一个非叶子节点
    for(int i = n / 2 - 1; i >= 0; i--)
    {
        MaxHeap(a,n,i);
    }   
    for(int i = n - 1; i >= 0; i--)
    {
        std::swap(a[0],a[i]);
        MaxHeap(a, i, 0);
    }
}

int main()
{
    int a[] = {5, 2, 1, 1, 4, 6, 3, 8, 2};
    HeapSort(a, sizeof(a) / sizeof(a[0]));
    for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    {
        std::cout<<a[i]<<" ";
    }
    std::cout<<std::endl;
    return 0;
}